#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int check(vector<int>& pos, int far)
    {
        int res = 1, pre = pos[0];
        for (auto& e : pos)
        {
            if (e - far >= pre)
            {
                ++res;
                pre = e;
            }
        }
        return res;
    }
    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(), position.end());
        int left = 0, right = position.back();
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            int put = check(position, mid);
            if (put >= m)
                left = mid + 1;
            else if (put < m)
                right = mid - 1;
        }
        return right;
    }
};